Non-volatile memory systems, such as flash memory, have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device.
Some flash memory management systems employ self-caching architectures where data received from a host is first stored in a portion of the flash memory designated as the cache and is later copied to a portion of the flash memory designated as a main storage area (such as a multi-level cell (MLC) type flash memory). In this type of flash memory management system, there is the question of when to schedule cache eviction operations. In cache eviction operations, a portion of the data in the cache, typically data corresponding to a common logical block, is copied from the cache to the main storage area and then removed from the cache to make room for new input data in the cache.
Self-caching flash memory management systems may employ different policies regarding the scheduling of cache eviction operations and regarding the selection of the specific data to be evicted. Typically, the factors influencing the scheduling decisions are how full the cache is, and whether there are access requests arriving from the host that have to be serviced. When the storage system is idle with respect to host requests, the flash memory management system may evict all data in the cache so that the cache is better prepared for a possible future burst of host activity.
Further, a current binary cache eviction algorithm attempts to provide the best gain in obsolete space by evicting: (1) the logical group (LG) with the highest number of fragments in the binary cache (BC) during a host operation (when the binary cache utilization threshold is exceeded); and (2) the logical group with the number of fragments exceeding a calculated threshold during idle time (when the idle time binary cache utilization threshold is exceeded).
The referenced current binary cache eviction algorithm may fail to select the logical groups best suited for eviction. This results in a reduction in the usable capacity, which may be defined as the maximum binary cache capacity minus the binary cache utilization threshold for logical group eviction. It further results in a higher frequency of binary cache evictions to the MLC (causing lower performance and reducing MLC endurance), and in a higher frequency of binary cache compactions and more data to copy (causing lower performance and reducing binary cache endurance). What is needed is a binary cache eviction operation that better selects entries in the binary cache for eviction.